package interview.duplicatenumber;

public class DuplicateNumber {
	public int duplicate(int[] array) {
		int ptr, i;
		ptr = -1;
		i = array[0] - 1;
		while(array[i] != 0) {
			if(ptr == -1 && i == array[i] - 1) {
				array[i] = 0;
				do {
					i++;
				} while(array[i] == 0);
			} else {
				ptr = array[i];
				array[i] = 0;
				i = ptr - 1;
			}
		}
		
		return i + 1;
	}
}
